/*******************************************************************************
 * Copyright (c) 2010-2011 Robert Fraser                                       *
 *                                                                             *
 * Permission is hereby granted, free of charge, to any person obtaining a     *
 * copy of this software and associated documentation files (the "Software"),  *
 * to deal in the Software without restriction, including without limitation   *
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,    *
 * and/or sell copies of the Software, and to permit persons to whom the       *
 * Software is furnished to do so, subject to the following conditions:        *
 *                                                                             *
 *   - The above copyright notice and this permission notice shall be included *
 *     in all copies or substantial portions of the Software.                  *
 *                                                                             *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR  *
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,    *
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER      *
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING     *
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER         *
 * DEALINGS IN THE SOFTWARE.                                                   *
 *******************************************************************************/

using System;
using System.Collections.Generic;

namespace zeal.util
{
    public sealed class MinHeap<T>
    {
        private readonly List<T> _values = new List<T>();
        private readonly Comparer<T> _comparer;

        public MinHeap() : this(null) { }
        public MinHeap(Comparer<T> comparer) { _comparer = comparer ?? Comparer<T>.Default; }

        public int length { get { return _values.Count; } }
        public void clear() { _values.Clear(); }

        public void push(T item)
        {
            _values.Add(item);
            int pos = length - 1;
            while (pos > 0)
            {
                int parent = (pos - 1) / 2;
                if (isGreater(pos, parent)) break;
                swap(pos, parent);
                pos = parent;
            }
        }

        public T peek() { T result; if(!peek(out result)) throw new InvalidOperationException("Heap is empty"); return result; }
        public bool peek(out T result)
        {
            if(length == 0)
            {
                result = default(T);
                return false;
            }
            result = _values[0];
            return true;
        }

        public T pop() { T result; if (!pop(out result)) throw new InvalidOperationException("Heap is empty"); return result; }
        public bool pop(out T result)
        {
            int len = length;
            if(len == 0)
            {
                result = default(T);
                return false;
            }
            int last = len - 1;
            result = _values[0];
            _values[0] = _values[last];
            _values.RemoveAt(last);
            int max = last / 2;
            int pos = 0;
            while(pos < max)
            {
                int child = 2 * pos + 1;
                if(child < (len - 2) && isGreater(child, child + 1)) child++;
                if(isGreater(child, pos)) break;
                swap(pos, child);
                pos = child;
            }
            return true;
        }

        private bool isGreater(int first, int second) { return _comparer.Compare(_values[first], _values[second]) > 0; }
        private void swap(int first, int second) { T temp = _values[first]; _values[first] = _values[second]; _values[second] = temp; }
    }
}